package mine.personal.demo.pratice.algorithm.twopointer;

import java.util.*;

public class Solution {



    /**
     * @description leetcode 四数之和
     * 这个题跟三数之和那道题非常像，只不过是最终nums[left]和nums[right]加起来不一样
     * 做这种题需要考虑溢出的风险。同时，这道题我并没有对j进行去重，因为主要我是用了hashset，本身hashset就具备了去重的功能~~~
     * @param nums
     * @param target
     * @return List<List<Integer>>
     * @author 李鸿麟
     * @since 2024/9/14     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        Set<List<Integer>> res = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j <= nums.length - 2; j++) {
                // if (j > 1 && nums[j] == nums[j - 1] ) {
                //     continue;
                // }
                int left = j + 1;
                int right = nums.length - 1;

                while (left < right) {
                    long sum = nums[left] + nums[right];
                    long aim = (long)target - nums[i] - nums[j];
                    if (sum > aim) {
                        right--;
                    } else if (sum < aim) {
                        left++;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;

                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }

                    }
                }

            }
        }

        return new ArrayList<>(res);
    }

    /**
     * @description leetcode 和为s的三个数
     * 这个题算法上与和为s的两个数那道题非常相似，也是利用单调性减少因为暴力枚举产生的时间复杂度，然后在去重的细节上需要注意
     * @param nums
     * @return List<List<Integer>>
     * @author 李鸿麟
     * @since 2024/9/13     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> res = new HashSet<>(); // 使用 HashSet 来存储结果

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 跳过重复的数字
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    // 找到了一个三元组
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;

                    // 跳过重复的数字 因为重复的数字不需要添加到list中，所以可以直接跳过，左右顺序其实没什么太大关系
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return new ArrayList<>(res); // 将结果转换为 List
    }


    /**
     * @description 剑指offer57 和为s的两个数字
     * 这题的思路和判断有效的三角形类似
     * @param arr
     * @param target
     * @return int[]
     * @author 李鸿麟
     * @since 2024/9/11     */
    public int[] twoSums(int[] arr, int target) {
        int left =0;
        int right = arr.length-1;
        while (left < right) {
            if (arr[left] + arr[right] < target) {
                left++;
            } else if(arr[left] + arr[right] > target){
                right--;
            } else {
                return new int[]{arr[left], arr[right]};
            }
        }
        return new int[]{0};
    }



    /**
     * @description leetcode 判断有效三角形的个数
     * 这个题的算法很有趣，涉及到一个数学原理。一个三角形的三边均满足两边之和大于第三边，如果这个题需要暴力解，那么当你拿到三个数，你就需要比对三次才能完全判断三个数字是否能组成一个三角形。
     * 但是，假如现在你知道这三个数字的大小顺序，如果较小的两条边的和 > 第三边，那么这三条边一定能组成一个三角形。
     * 所以，先对数组排序，方便确定最大的数字max，如果left和right对应的数字大于max，那么right-left这个区间里所有的数字一定都能符合要求（因为数组是升序的）
     * @param nums
     * @return int
     * @author 李鸿麟
     * @since 2024/9/11     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        int sum;

        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    res += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return res;
    };




    /**
     * @description leetcode 盛最多水的容器
     * 核心思想：木板原理
     * 面对这个题目，容积V=底 * 高。 底 = right-left, 高是right和left对应元素中相对小的那一个。于是，在这种情况下，高在每一趟循环中的是可以被确定的。
     * 但是在这个题目中，由于left和right对应的高度未知，所以可能出现一个容器虽然底很窄但是高度很高的情况，于是就需要一个循环，判断left和right在相遇之前计算出现的容积，最后求最大值就可以
     * @param height
     * @return int
     * @author 李鸿麟
     * @since 2024/9/9     */
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxVolume = 0;

        while (left < right) {
            // 计算当前的体积
            int currentVolume = (right - left) * Math.min(height[left], height[right]);
            maxVolume = Math.max(maxVolume, currentVolume);

            // 移动较小的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxVolume;
    }

    /**
     * @description  leetcode 快乐数
     *  核心逻辑:鸽巢原理
     *  依据题目要求，在数据范围内最大的数字是9999999999。依据题目意思，此时9999999999的每一位上的平方和为810，即在1-9999999999的数字范围内能产生平方数的集合为[1, 810]
     *  而在区间[1, 810]中假设存在一个数，他经过了810次变化后依旧没有重复，那么再进行第811次变化的时候，他一定会变成之前出现过的数字(所有的替身都被用光了)
     *  在这种情况下，这个数字的变化情况就会变成一个环，而此题的解决方法就变成了类似于判断一个链表中有没有环，如果有环，且快慢指针相遇时均为1，那么这个数就是快乐数
     * @return boolean
     * @author 李鸿麟
     * @since 2024/9/9     */
    public boolean isHappy(int n) {
        int fast = bitSum(n);
        int slow = n;

        while (slow != fast) {
            fast = bitSum(bitSum(fast));
            slow = bitSum(slow);
        }
        return slow == 1;
    }
    public int bitSum(int n) {
        int sum = 0;
        while(n != 0) {
            int t = n%10;
            sum += t * t;
            n = n / 10;
        }
        return sum;
    }


    /**
     * @description  leetcode 复写零
     * @author 李鸿麟
     * @since 2024/9/9     */
    public void duplicateZeros(int[] arr) {
        int cur = 0; int ep = -1; int n = arr.length;
        // 1.找到结果数组中最后一个数字
        while(cur < n) {
            if(arr[cur] != 0) {
                ep++;
            } else {
                ep+=2;
            }
            if(ep >= arr.length-1) break;
            cur++;
        }

        // 2.处理边界情况
        if(ep == n) {
            arr[n-1] = 0;
            cur--;
            ep-=2;
        }

        // 3.从后往前复写，避免从前往后覆盖非零元素
        while(cur >= 0) {
            if(arr[cur] != 0) {
                arr[ep--] = arr[cur--];
            } else{
                arr[ep--] = 0;
                arr[ep--] = 0;
                cur--;
            }
        }
    }

    /**
     * 找到所有的单词的异位词
     * @param ss 匹配串
     * @param pp 目标子串
     * @return List<Integer>
     * @author 李鸿麟
     * @since 2025/3/11     */
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        int left = 0, right = 0;
        // 有效字符的个数 即s中与p中一致的字母，且个数与s相同
        int count = 0;

        // 准备字符串以及哈希表
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // hash1 用于记录p的字符情况 这里的hash用字符数组替代 利用了哈希值和字母本身的特点 下标是字母表中字母的字典序位置 值是出现的次数
        int[] hash1 = new int[26];

        // hash2 用于记录s的字符情况 原理同hash1
        int[] hash2 = new int[26];
        for(char ch : p){ hash1[ ch - 'a' ]++; }
        int m = p.length;

        // 准备滑动窗口 进行遍历
        for (; right < ss.length(); right++) {
            //进窗口
            char in = s[right];
            // 如果当前进入的是有效字符 count就++
            // 提示：这个地方的++写法是两步并做一步写了 一开始不是这样的
            if (++hash2[in - 'a'] <= hash1[in - 'a']) {
                count++;
            }

            // 出窗口
            if (right - left + 1 > m) {
                // 这个地方的left++原理同上面的right++
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count --;
                }
            }

            // 更新结果
            if (count == m) {
                ret.add(left);
            }

        }

        return ret;
    }

    /**
     * 串联所有单词的子串
     * @param ss 匹配串
     * @param words 目标字符数组
     * @return List<Integer>
     * @author 李鸿麟
     * @since 2025/3/11     */
    public List<Integer> findSubstring(String ss, String[] words) {
        List<Integer> ret = new ArrayList<>();

        // 1.准备哈希表 用于统计words数组中单词出现的次数
        // hash1 -> words; hash2 -> s
        Map<String, Integer> hash1 = new HashMap<>();
        for (String string : words) {
            hash1.put(string, hash1.getOrDefault(string, 0) + 1);
        }
        int length = words[0].length(), m = words.length;
        // 2.准备滑动窗口
        for (int i = 0; i < length; i++) {
            Map<String, Integer> hash2 = new HashMap<>();
            for (int left = i, right = i, count = 0; right + length <= ss.length(); right += length) {
                // 进窗口
                String in = ss.substring(right, right + length);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                // 维护count
                if (hash2.get(in) <= hash1.getOrDefault(in ,0)) {
                    count++;
                }
                //判断是不是要出窗口
                if (right - left + 1 > m * length) {
                    String out = ss.substring(left, left + length);
                    //维护count
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += length;
                }
                //更新结果
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    /**
     * 最小覆盖子串
     * @param s 目标串
     * @param t 匹配串
     * @return String
     * @author 李鸿麟
     * @since 2025/3/13     */
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        Map<Character, Integer> hash1 = new HashMap<>();
        Map<Character, Integer> hash2 = new HashMap<>();
        // 准备哈希表
        for(char i : tt) {
            hash2.put(i, hash2.getOrDefault(i,0)+1);
        }
        // minLen=>最小子串的长度 begin=>最小子串的起始位置
        int minLen = Integer.MAX_VALUE, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.length(); right++) {
            // 进窗口
            char in = ss[right];
            hash1.put(in, hash1.getOrDefault(in,0)+1);
            if(hash2.containsKey(in) && hash1.get(in).equals(hash2.get(in))){
                count++;
            }
            // 这个地方是滑动窗口的精髓 因为当left移动的时候 新得到的子串要么符合要求 要么不符合要求 得出来的right运动规律就是要么不变 要么+1 所以需要一个循环把right卡住不动
            while(count == hash2.size()){
                // 更新一下结果
                char out = ss[left];
                if (minLen > right - left + 1) {
                    minLen = right - left + 1;
                    begin = left;
                }
                // 维护count
                if(hash1.get(out).equals(hash2.get(out))){
                    count--;
                }
                hash1.put(out, hash1.getOrDefault(out, 1) - 1);
                left++;
            }
        }

        return begin == -1 ? "" : s.substring(begin, begin + minLen);
    }


}
